Prédiction de type on-policy par approximations

3. Fonction objectif de prédiction

Nécessité d'utiliser une fonction objectif

Dans le cas de la mise à jour des valeurs des états discrets sous forme de table, juger de la qualité des prédictions n'était pas nécessaire parce que la fonction des valeurs des états apprise convergeait vers la vraie valeur. De plus, la mise à jour de chacun des états de faisait indépendamment des autres.

Mais comme nous l'avons déjà vu, ce n'est pas le cas dans les méthodes que nous allons mettre en oeuvre : on peut pas obtenir la valeur exacte des états et la modification d'un état spécifique engendre la modification de tous les états de l'environnement. Cela vient du fait que la dimension du vecteur contenant les poids qui sont utilisés pour adapter la fonction approximée est beaucoup plus petite que le nombre total d'états de l'environnement. Par conséquent, faire en sorte de rendre la valeur d'un état plus précise a pour conséquence de diminuer la précision de l'estimation des autres états.

Nous sommes donc obligés d'utiliser une méthode nous permettant de mesurer la qualité de l'approximation sur l'ensemble des états de l'environnement. Nous devons également préciser les états pour lesquels nous souhaitons apporter le plus d'importance lors de l'estimation. Pour cela on utilise une distribution $\mu \left( s \right) \ge 0, \: \sum\limits_s {\mu \left( s \right) = 1}$ qui va nous permettre de quantifier l'importance de chacun des états.

Pour mesurer l'erreur de l'estimation des valeurs des états réalisée par la fonction approximée $\hat v\left( {s,{\textbf{w}}} \right)$, on utilise une fonction objectif qui va permettre de la comparer à la vraie valeur $V_\pi(s)$. La fonction d'objectif est définie par :

$$\overline {VE} \left( \textbf{w} \right) = \sum\limits_{s \in S} {\mu \left( s \right){{\left[ {{V_\pi }\left( s \right) - \hat v\left( {s,\textbf{w}} \right)} \right]}^2}}$$

C'est la racine carrée de cette mesure que nous prendrons pour estimer l'erreur. Souvent la distribution $\mu \left( s \right)$ est choisie égale à la fraction du temps passé par l'agent sur un état $s$. Lorsque l'apprentissage est de type on-policy, cette distribution est appelée distribution on-policy. Dans le cas des tâches continues, cette distribution prend pour valeur la distribution stationnaire obtenue sous la stratégie $\pi$.

Distribution on-policy dans le cas des tâches épisodiques

Lorsque les tâches sont épisodiques, la distribution on-policy va dépendre de la manière dont les états initiaux sont choisis lors de l'épisode. Si on appelle :

  • $h(s)$ la probabilité que l'état $s$ soit choisi au début de l'épisode
  • $\eta \left( s \right)$ le nombre moyen d'instants passés sur l'état $s$ pendant cet épisode

Comme le temps s'écoule sur un état $s$ si l'épisode démarre sur ce même état ou si une transition est faite sur cet état depuis un état précédent $\overline s $, alors le nombre d'instants passés sur l'état $s$ est donné par :

$$\eta \left( s \right) = h\left( s \right) + \sum\limits_s {\eta \left( {\overline s } \right)} \sum\limits_a {\pi \left( {a|\overline s } \right)} p\left( {s|\overline s ,a} \right),\:\forall s \in S$$

Le système d'équations peut être résolu pour trouver le nombre de visites $\eta \left( s \right)$. La distribution on-policy est ensuite calculée comme étant la fraction du temps passé dans chaque état divisé par la somme temps passé dans l'ensemble des états afin de la normaliser à l'unité :

$$\mu \left( s \right) = \frac{{\eta \left( s \right)}}{{\sum\limits_{s'} {\eta \left( {s'} \right)} }},\: \forall s \in S$$

Ici pas tenu compte du facteur de remise. Dans le cas où le facteur de remise γ < 1, on l'inclut dans l'expression précédente de la manière suivante :

$$\eta \left( s \right) = h\left( s \right) + \gamma \sum\limits_s {\eta \left( {\overline s } \right)} \sum\limits_a {\pi \left( {a|\overline s } \right)} p\left( {s|\overline s ,a} \right)$$

Optimum global et local

Idéalement, la fonction objectif $\overline {VE}$ devrait trouver un optimum global, c'est-à-dire trouver le vecteur poids $\textbf{w*}$ pour lequel $\overline {VE} \left( \textbf{w*} \right) \le \overline {VE} \left( \textbf{w} \right)$ pour n'importe quel $\textbf{w}$ possible. Atteindre cet objectif est quelquefois possible lorsque les fonctions d'approximation utilisées sont linéaires, mais cela est rarement possible dans les cas plus complexes comme par exemple lorsqu'on utilise des réseaux de neurones artificiels ou des arbres de décisions.

On cherche alors plutôt à faire en sorte que les fonctions approximées convergent vers un optimum local, c'est-à-dire trouver le vecteur poids $\textbf{w*}$ pour lequel $\overline {VE} \left( \textbf{w*} \right) \le \overline {VE} \left( \textbf{w} \right)$ pour les $\textbf{w}$ au voisinage de $\textbf{w*}$. C'est la meilleure des solutions que nous pouvons obtenir lorsqu'on utilise des approximations non linéaires et cela est souvent suffisant.

Précisons cependant que rien ne permet d'assurer la convergence vers un optimum dans tous les cas, ni même de se rapprocher suffisamment de $\textbf{w*}$. Certaines méthodes divergent même.

Méthodes d'approximations

Les différentes méthodes d'approximation des fonctions sont nombreuses et nous ne traiterons que certaines d'entre elles. Nous utiliserons celles basées sur la méthode du gradient, en particulier la méthode par descente du gradient linéaire.